//给你一个整数数组 nums，请你将该数组升序排列。 
//
// 
//
// 
// 
//
// 示例 1： 
//
// 
//输入：nums = [5,2,3,1]
//输出：[1,2,3,5]
// 
//
// 示例 2： 
//
// 
//输入：nums = [5,1,1,2,0,0]
//输出：[0,0,1,1,2,5]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 5 * 10⁴ 
// -5 * 10⁴ <= nums[i] <= 5 * 10⁴ 
// 
//
// Related Topics 数组 分治 桶排序 计数排序 基数排序 排序 堆（优先队列） 归并排序 👍 854 👎 0


import java.util.concurrent.ThreadLocalRandom;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[] sortArray(int[] nums) {
        int j=nums.length-1;
        //冒泡排序 总的来说就是两轮循环遍历每个元素 优化就是使用i来记录i的位置 因为i的位置会到达已排序数组的边界
//        while(true){
//            int x=0;
//            for (int i = 0; i <j; i++) {
//                if(nums[i]>nums[i+1]){
//                    swap(nums,i,i+1);
//                }
//                x=i;
//            }
//            j=x;
//            if(j==0){
//                break;
//            }
//        }
//        return nums;

        //选择排序  外循环从尾往前开始遍历并作为最大的值 内循环从开头开始遍历 以此比较并更新最大值 遍历完毕后 和最右边的下标交换 实现选择出最大的值
//        for (int right = j; right >0; right--) {
//            int max=right;
//            for (int k = 0; k < right; k++) {
//                if(nums[k]>nums[max]){
//                    max=k;
//                }
//            }
//            if(max!=right){
//                swap(nums,max,right);
//            }
//        }
//        return nums;

        //插入排序   从下标1开始 其前面的作为已排序的区域 从1以后遍历每个元素 与已排序区域比较 找到合适的位置插入
//        for (int i = 1; i <=j ; i++) {
//            int cur=nums[i];
//            int pre=i-1;
//            while (pre>=0&&nums[pre]>cur){
//                nums[pre+1]=nums[pre];
//                pre--;
//            }
//            if(pre!=i-1){
//                nums[pre+1]=cur;
//            }
//        }
//        return nums;

        //希尔排序
//        for (int gap = nums.length>>1; gap >0 ; gap=gap>>1) {
//            for (int low = gap; low <nums.length ; low++) {
//                int last=nums[low];
//                int pre=low-gap;
//                while (pre>=0&&nums[pre]>last){
//                    nums[pre+gap]=nums[pre];
//                    low-=gap;
//                }
//                if(pre!=low-gap){
//                    nums[pre+gap]=last;
//                }
//            }
//        }
//        return nums;

        //堆排序
//            int size=nums.length;
//            for (int i = nums.length/2-1; i >=0 ; i--) {
//                down(nums,i,size);
//            }
//
//            for (int i = size-1; i >0 ; i--) {
//                swap(nums,0,i);
//                down(nums,0,i);
//            }
//
//            return nums;
        //快速排序
//        quick(nums,0,nums.length-1);

        return nums;

    }
//    public void quick(int[] nums,int left,int right){
//        if (left >= right) {
//            return;
//        }
//        int p = partition(nums, left, right);
//        quick(nums, left, p - 1);
//        quick(nums, p + 1, right);
//    }

//    public int partition(int[] nums,int left,int right ){
//        int index = ThreadLocalRandom.current().nextInt(right - left + 1) + left;
//        swap(nums,left,index);
//        int pv=nums[left];
//        int i=left+1;
//        int j=right;
//        while (i<=j){ //=是因为 最后需要确定 j的位置 便于和基准点交换位置
//            while (i<=j&&nums[i]<pv){
//                i++;
//            }
//            while (i<=j&&pv<nums[j]){//j找小的
//                j--;
//            }
//            if(i<=j){
//                swap(nums,i,j);
//                i++;
//                j--;
//            }
//        }
//        swap(nums,j,left);
//        return j;
//
//
//    }

//    public void down(int[] nums,int parent,int size){
//        while (true){
//            int left=parent*2+1;
//            int right=left+1;
//            int max=parent;
//            if(left<size&&nums[max]<nums[left]){
//                max=left;
//            }
//            if(right<size&&nums[max]<nums[right]){
//                max=right;
//            }
//            if(max==parent){
//                break;
//            }
//            swap(nums,max,parent);
//            parent=max;
//        }
//    }

//    public void swap(int[] nums,int i,int j){
//        nums[i]=nums[i]^nums[j];
//        nums[j]=nums[j]^nums[i];
//        nums[i]=nums[i]^nums[j];
//    }

    private static void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
